SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Live-variable analysis</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Live-variable analysis</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Compilers" class="mw-redirect" title="Compilers">compilers</a>, <b>live variable analysis</b> (or simply <b>liveness analysis</b>) is a classic <a href="Data-flow_analysis" title="Data-flow analysis">data-flow analysis</a> to calculate the <a href="Variable_(programming)" class="mw-redirect" title="Variable (programming)">variables</a> that are <i>live</i> at each point in the program. A variable is <i>live</i> at some point if it holds a value that may be needed in the future, or equivalently if its value may be read before the next time the variable is written to.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>Consider the following program:

</p>

<pre>b = 3

c = 5

a = f(b * c)

</pre>

<p>The set of live variables between lines 2 and 3 is {<code>b</code>, <code>c</code>} because both are used in the multiplication on line 3. But the set of live variables after line 1 is only {<code>b</code>}, since variable <code>c</code> is updated later, on line 2. The value of variable <code>a</code> is not used in this code.

</p><p>Note that the assignment to <code>a</code> may be eliminated as <code>a</code> is not used later, but there is insufficient information to justify removing all of line 3 as <code>f</code> may have <a href="Side_effect_(computer_science)" title="Side effect (computer science)">side effects</a> (printing <code>b * c</code>, perhaps).

</p>

<div class="mw-heading mw-heading2"><h2 id="Expression_in_terms_of_dataflow_equations">Expression in terms of dataflow equations</h2></div>

<p>Liveness analysis is a "backwards may" analysis. The analysis is done in a <a href="Data-flow_analysis#Backward_Analysis" title="Data-flow analysis">backwards</a> order, and the dataflow confluence operator is <a href="Set_union" class="mw-redirect" title="Set union">set union</a>. In other words, if applying liveness analysis to a function with a particular number of logical branches within it, the analysis is performed starting from the end of the function working towards the beginning (hence "backwards"), and a variable is considered live if any of the branches moving forward within the function might potentially (hence "may") need the variable's current value. This is in contrast to a "backwards must" analysis which would instead enforce this condition on all branches moving forward.

</p><p>The dataflow equations used for a given basic block <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math></span><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"></span> and exiting block <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathit {final}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathit {final}}}</annotation>

</semantics>

</math></span><img src="./e3136e7cbde4de869aa3bf31e0d625909f803252.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.052ex; margin-right: -0.13ex; width:4.701ex; height:2.509ex;" alt="{\displaystyle {\mathit {final}}}" loading="lazy"></span> in live variable analysis are the following:

</p>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{GEN}}[s]}</annotation>

</semantics>

</math></span><img src="./bde42b503e6ae65f77c0c3fa767a2d0fc9b9f9a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.534ex; height:2.843ex;" alt="{\displaystyle {\mbox{GEN}}[s]}" loading="lazy"></span>: The set of variables that are used in s before any assignment in the same basic block.</dd></dl>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{KILL}}[s]}</annotation>

</semantics>

</math></span><img src="./843c3e280d6ed7c2e7e42c116ab3fa86cbc07e41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.937ex; height:2.843ex;" alt="{\displaystyle {\mbox{KILL}}[s]}" loading="lazy"></span>: The set of variables that are assigned a value in s (in many books that discuss compiler design, KILL (s) is also defined as the set of variables assigned a value in s <i>before any use</i>, but this does not change the solution of the dataflow equation):</dd></dl>

<p><br>

</p>

<msub>

</mstyle>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<msub>

</mstyle>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{LIVE}}_{\mathrm {in} }[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{\mathrm {out} }[s]-{\mbox{KILL}}[s])}</annotation>

</semantics>

</math></span><img src="./59c576d16331888525fdfa06581ffde433413671.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:46.019ex; height:2.843ex;" alt="{\displaystyle {\mbox{LIVE}}_{\mathrm {in} }[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{\mathrm {out} }[s]-{\mbox{KILL}}[s])}" loading="lazy"></span></dd>

<msub>

</mstyle>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[{\mathit {final}}]={\emptyset }}</annotation>

</semantics>

</math></span><img src="./92a557403d651388253c7bb17e22e59add7e67e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.299ex; height:2.843ex;" alt="{\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[{\mathit {final}}]={\emptyset }}" loading="lazy"></span></dd>

<msub>

</mstyle>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mstyle>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[s]=\bigcup _{p\in \mathrm {succ} [s]}{\mbox{LIVE}}_{\mathrm {in} }[p]}</annotation>

</semantics>

</math></span><img src="./24b853bf17f1b7fc6061fcd01fa571a39da7ce20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:30.412ex; height:6.009ex;" alt="{\displaystyle {\mbox{LIVE}}_{\mathrm {out} }[s]=\bigcup _{p\in \mathrm {succ} [s]}{\mbox{LIVE}}_{\mathrm {in} }[p]}" loading="lazy"></span></dd></dl>

</mstyle>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}</annotation>

</semantics>

</math></span><img src="./3f5c01720a2c3843fa99038c8887eba960719607.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.09ex; height:2.843ex;" alt="{\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}" loading="lazy"></span></dd>

</mstyle>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}</annotation>

</semantics>

</math></span><img src="./b9f993860dfa62f1c430a9b805e8684346a1d87d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.547ex; height:2.843ex;" alt="{\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}" loading="lazy"></span></dd></dl>

<p>The in-state of a block is the set of variables that are live at the start of the block. Its out-state is the set of variables that are live at the end of it. The out-state is the union of the in-states of the block's successors. The transfer function of a statement is applied by making the variables that are written dead, then making the variables that are read live.

</p>

<div class="mw-heading mw-heading2"><h2 id="Second_example">Second example</h2></div>

<table>

<td>

<pre>// in: {}; predecessor blocks: none

b1: a = 3;

b = 5;

d = 4;

x = 100; //x is never being used later thus not in the out set {a,b,d}

if a > b then

// out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}

// in: {a,b}; predecessor blocks: b1

b2: c = a + b;

d = 2;

// out: {b,d}

// in: {b,d}; predecessor blocks: b1 and b2

b3: endif

c = 4;

return b * d + c;

// out:{}

</pre>

</td></tr></tbody></table>

<p>The in-state of b3 only contains <i>b</i> and <i>d</i>, since <i>c</i> has been written. The out-state of b1 is the union of the in-states of b2 and b3. The definition of <i>c</i> in b2 can be removed, since <i>c</i> is not live immediately after the statement.

</p><p>Solving the data flow equations starts with initializing all in-states and out-states to the empty set. The work list is initialized by inserting the exit point (b3) in the work list (typical for backward flow). Its computed in-state differs from the previous one, so its predecessors b1 and b2 are inserted and the process continues. The progress is summarized in the table below.

</p>

<th>processing

</th>

<th>out-state

</th>

<th>old in-state

</th>

<th>new in-state

</th>

<th>work list

</th></tr>

<tr>

<td>b3

</td>

<td>{}

</td>

<td>{}

</td>

<td>{b,d}

</td>

<td>(b1,b2)

</td></tr>

<tr>

<td>b1

</td>

<td>{b,d}

</td>

<td>{}

</td>

<td>{}

</td>

<td>(b2)

</td></tr>

<tr>

<td>b2

</td>

<td>{b,d}

</td>

<td>{}

</td>

<td>{a,b}

</td>

<td>(b1)

</td></tr>

<tr>

<td>b1

</td>

<td>{a,b,d}

</td>

<td>{}

</td>

<td>{}

</td>

<td>()

</td></tr></tbody></table>

<p>Note that b1 was entered in the list before b2, which forced processing b1 twice (b1 was re-entered as predecessor of b2). Inserting b2 before b1 would have allowed earlier completion.

</p><p>Initializing with the empty set is an optimistic initialization: all variables start out as dead. Note that the out-states cannot shrink from one iteration to the next, although the out-state can be smaller than the in-state. This can be seen from the fact that after the first iteration the out-state can only change by a change of the in-state. Since the in-state starts as the empty set, it can only grow in further iterations.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAhoLamSethiUllman2007" class="citation book cs1">Aho, Alfred; Lam, Monica; Sethi, Ravi; Ullman, Jeffrey (2007). <i>Compilers: Principles, Techniques, and Tools</i> (2 ed.). p. 608.</cite>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Compiler_optimizations253" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Compiler_optimizations253" style="font-size:114%;margin:0 4em"><a href="Optimizing_compiler" title="Optimizing compiler">Compiler optimizations</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic block</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Local_value_numbering" class="mw-redirect" title="Local value numbering">Local value numbering</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Loop_optimization" title="Loop optimization">Loop</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Automatic vectorization</a></li>

<li><a href="Induction_variable" title="Induction variable">Induction variable</a></li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Loop fusion</a></li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a></li>

<li><a href="Loop_inversion" title="Loop inversion">Loop inversion</a></li>

<li><a href="Loop_interchange" title="Loop interchange">Loop interchange</a></li>

<li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Loop_splitting" title="Loop splitting">Loop splitting</a></li>

<li><a href="Loop_unrolling" title="Loop unrolling">Loop unrolling</a></li>

<li><a href="Loop_unswitching" title="Loop unswitching">Loop unswitching</a></li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a></li>

<li><a href="Strength_reduction" title="Strength reduction">Strength reduction</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow<br>analysis</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Common_subexpression_elimination" title="Common subexpression elimination">Common subexpression elimination</a></li>

<li><a href="Constant_folding" title="Constant folding">Constant folding</a></li>

<li><a href="Dead_store" title="Dead store">Dead store</a> elimination</li>

<li><a href="Induction_variable_recognition_and_elimination" class="mw-redirect" title="Induction variable recognition and elimination">Induction variable recognition and elimination</a></li>

<li><a href="Upwards_exposed_uses" title="Upwards exposed uses">Upwards exposed uses</a></li>

<li><a href="Use-define_chain" title="Use-define chain">Use-define chain</a></li>

<li><a href="Reaching_definition" title="Reaching definition">Reaching definitions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Static_single-assignment_form" title="Static single-assignment form">SSA</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Global_value_numbering" class="mw-redirect" title="Global value numbering">Global value numbering</a></li>

<li><a href="Sparse_conditional_constant_propagation" title="Sparse conditional constant propagation">Sparse conditional constant propagation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Code_generation_(compiler)" title="Code generation (compiler)">Code generation</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Instruction_scheduling" title="Instruction scheduling">Instruction scheduling</a></li>

<li><a href="Instruction_selection" title="Instruction selection">Instruction selection</a></li>

<li><a href="Register_allocation" title="Register allocation">Register allocation</a></li>

<li><a href="Rematerialization" title="Rematerialization">Rematerialization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Functional</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deforestation_(computer_science)" title="Deforestation (computer science)">Deforestation</a></li>

<li><a href="Tail_call" title="Tail call">Tail-call elimination</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Global</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interprocedural_optimization" title="Interprocedural optimization">Interprocedural optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a></li>

<li><a href="Compile-time_function_execution" title="Compile-time function execution">Compile-time function execution</a></li>

<li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Expression_templates" title="Expression templates">Expression templates</a></li>

<li><a href="Inline_expansion" title="Inline expansion">Inline expansion</a></li>

<li><a href="Jump_threading" title="Jump threading">Jump threading</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li>

<li><a href="Profile-guided_optimization" title="Profile-guided optimization">Profile-guided optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Static analysis</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alias_analysis" title="Alias analysis">Alias analysis</a></li>

<li><a href="Array-access_analysis" title="Array-access analysis">Array-access analysis</a></li>

<li><a href="Control-flow_analysis" title="Control-flow analysis">Control-flow analysis</a></li>

<li><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow analysis</a></li>

<li><a href="Dependence_analysis" title="Dependence analysis">Dependence analysis</a></li>

<li><a href="Escape_analysis" title="Escape analysis">Escape analysis</a></li>

<li><a href="Pointer_analysis" title="Pointer analysis">Pointer analysis</a></li>

<li><a href="Shape_analysis_(program_analysis)" title="Shape analysis (program analysis)">Shape analysis</a></li>

<li><a href="Value_range_analysis" title="Value range analysis">Value range analysis</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-09" href="https://en.wikipedia.org/wiki/?title=Live-variable_analysis&oldid=1294710587">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>